#!/usr/bin/env python2.5
#Noah Gift
#Recursive Greedy Coin Match

import sys
import decimal

class Change():

    def __init__(self, amount):
        self.amount = amount
        self.convert = int(amount*100)
        self.coins = [1,5,10,25]
        self.coin_lookup = {25: "quarters", 10: "dimes", 5: "nickels", 1: "pennies"}

    def printer(self, num, coin):
        if num:
            if coin in self.coin_lookup:
                print num, self.coin_lookup[coin]

    def while_change(self):
        """Greedy Coin Match with Recursion"""
        coin = self.coins.pop()
        num, rem  = divmod(self.convert, coin)
        self.printer(num,coin)
        while rem > 0:
            coin = self.coins.pop()
            num, rem = divmod(rem, coin)
            self.printer(num,coin)

    def recursive_change(self, rem):
        if len(self.coins) == 0:
            return []
        coin = self.coins.pop()
        num, new_rem = divmod(rem, coin)
        self.printer(num,coin)
        return self.recursive_change(new_rem) + [num]

if __name__ == "__main__":
    amount = decimal.Decimal(sys.argv[1])
    convert = int(amount*100)
    c = Change(amount)
    print "While Loop:"
    c.while_change()

    print "Recursive:"
    c.recursive_change(convert)
